#include <stdio.h>

/*快速排序函数声明*/
void quickSort(int arr[], int size);
/*快速排序递归函数声明*/
void subSort(int arr[], int start, int end);

/**
***********************************************************************
* @brief   快速排序函数
* @param   int arr[], int size
* @retval  无
* @note  
***********************************************************************
*/
void quickSort(int arr[], int size)
{
	subSort(arr, 0, size - 1);
}

/**
***********************************************************************
* @brief   快速排序递归函数
* @param   int arr[], int start, int end
* @retval  无
* @note  
***********************************************************************
*/
void subSort(int arr[], int start, int end)
{
	/*递归结束条件：*/
	if(start < end)
	{
		int base = arr[start];//将快速排序的基准定义为数组的第一个元素
		int low = start;
		int high = end + 1;

		/*假如low >= high时，循环跳出*/
		while(1)
		{
			while(low < end && arr[++low] < base);//从前往后找到第一个比基准base大的值
			while(high > start && arr[--high] > base);//从后往前找到第一个比基准base小的值
			/*如果low比high小，交换这两个的值*/
			if(low < high)
			{
				int temp = arr[low];
				arr[low] = arr[high];
				arr[high] = temp;
			}
			else
			{
				break;
			}
		}

		/*交换arr[start]和arr[high]的值*/
		int temp1 = arr[start];
		arr[start] = arr[high];
		arr[high] = temp1;

		/*递归调用自己*/
		subSort(arr, start, high - 1);//左边部分数据区间递归调用
		subSort(arr, high + 1, end);//右边部分数据区间递归调用	
	}
}

int main(void)
{
	int arr[5] = {20, 60, 40, 30 , 10};
	quickSort(arr, 5);
	for(int i = 0; i <  5; i++)
	{
		printf("%d ", arr[i]);
	}
	return 0;
}